<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8">
   <META NAME="Author" CONTENT="Maciej Drozdowski">
   <link rel="stylesheet" type="text/css" href="styl.css">
</HEAD>
<body>
<h2>
Laboratorium optymalizacja kombinatoryczna, 2011/2012
</h2>
<a href="#zas">Zasady zaliczenia</a> &nbsp;&nbsp;
<a href="#sprawo">Format sprawozdania</a> &nbsp;&nbsp;
<a href="#tema">Tematy zadań</a> &nbsp;&nbsp;
<a href="#info">Uwagi</a> &nbsp;&nbsp;
<br>

<hr>
<a name="zas"></a>
<b>Zasady zaliczania</b>
<br>
<p>
<ol>
<li>Grupa dziekańska jest dzielona na 2-sobowe zespoły. 
Każdy zespół programuje przynajmniej 2 rozwiązania dla jednego z 3 problemów.

<li>Oceny określane są następująco. 
Wyliczana jest średnia z ocen za rozwiązania.
Dwa rozwiązania są obowiązkowe, trzecie rozwiązanie dla chętnych (np. w celu
podwyższenia średniej). 
Brak rozwiązania oznacza ocenę 2.0.
Do oceny średniej za programy mogą być dodane punkty: 
a) +1 dla zespołu, który jako pierwszy zrobi 1 metodę, 
b) +0.5 dla zespołu, który jako drugi zrobi 1 metodę,
c) za szczególnie ciekawe rozwiązania (b. szybkie, b. dobrej jakości, ciekawa idea metody),
d) +1 za zanalezienie błędu w sprawdzarce.


<li>Poszczególne rozwiązania muszą się istotnie różnić jakościowo. Na przykład,
użycie heurystyki kolorującej wierzchołki grafu w kolejności wynikającej z
czegoś jest tylko jedną metodą niezależnie od metody wyboru kolejności wierzchołków.
Trzy różne metaheurystki (np. simulated annealing, tabu search i genetic
algorithm) SĄ trzema różnymi metodami. Co do różnych wersji algorytmu BB, to
istnienie różnic między implementacjami jest zależne od szczegółów, 
tj. metod cięcia i liczenia dolnych ograniczeń.          

<li>Aby rozwiązanie zostało przyjęte należy:
<ul>
<li>na zajęciach pokazać program w działaniu na testach,
<li>ustnie objaśnić zasadę działania kodu na zajęciach,
<li>przysłać emailem kod do teststów sprawdzarką,
<li>sporządzić sprawozdanie.
</ul>

<li><b>Terminy zaliczenia</b>.<ul>
 <li>Pierwsze rozwiązanie powinno być zaliczone do <u>19 XI 2011</u>.
 <li>Drugie i ewentualne trzecie rozwiązanie do <u>10 XII 2011</u>.
</ul> 
Do tych terminów powinny być zaliczone
wszystkie powyższe kroki weryfikujące rozwiązanie.
Programy można też zaliczać wcześniej.

<li>Każdy tydzień opóźnienia w zaliczeniu obniża ocenę o 0.5. 
Jeżeli praca była zwrócona do poprawki (tzn. musi być oceniona ponownie), to
nową wersję trzeba dostarczyć w ciągu tygodnia od wysłania przeze mnie
informacji o błędach. Przekroczenie tego terminu będzie obniżać ocenę
bazową o 0.5 stopnia za każdy tydzień.
Minimalna ocena pracy, która (w końcu) zostanie zaakceptowana wynosi 3.0.

<li>
Daty wpłynięcia sprawozdania, programu, wysłania informacji o
błędach określa mój system poczty elektronicznej lub (w przypadku
papieru) moment wręczenia sprawozdania (datę na nim możemy wpisać razem ;-).
Jako ostateczna data wpłynięcia rozwiązania brany jest zawsze termin
dostarczenia ostatniego elemntu weryfikacji rozwiązania.
Innymi słowy, jeżeli praca jest oddawana w kawałkach (program, tekst), to liczy
się data oddania ostatniego kawałka.

<li>
Po zakończeniu sesji poprawkowej prace nie będą przyjmowane.

<Li>
Sprawozdanie może być tworzone przyrostowo, tzn. sprawozdanie dla każdego
kolejnego rozwiązania może zawierać poprzednie sprawozdanie jako podzbiór.

<li>Język programowania C, C++, kompilator gcc, g++ dla środowiska Linux, Cygwin.
Akceptowane będą tylko te programy, które uda się skompilować na zajęciach
dostępnymi kompilatorami.
Wszystkie programy muszą się dać wykonać z linii poleceń i z linii
poleceń przyjmować parametry wykonania (nazwy plików, liczby, itp.).

<li>Jakie metody wchodzą w rachubę:<br> 
a) "szyte" heurystyki,<br> 
b) BB,<br> 
c) metaheurystyki,<br> 
d) użycie zewnętrznych pakietów rozwiązujących części składowe problemu np. (sprowadzenie do) 
ILP (integer linear programming, np. 
<a href="http://lpsolve.sourceforge.net/5.5/">lp_solve</a>
przykład <a href="knapsack1.lp">knapsack</a>,
przykład <a href="max-sat1.lp">max-sat</a>).<br> 
Pobieżny opis tych metod można znaleźć np. na foliach 60-96 na stronie z prowadzonego kiedyś przeze mnie 
<a href="http://www.cs.put.poznan.pl/mdrozdowski/dyd/420/szere.html">wykładu</a>. 

<li>
Zalecenie: 
Najlepiej, aby pierwszą metodą był szyta/zachłanna heurystyka,

<li>
Uwaga!  
Nie wolno importować całych gotowych rozwiązań (cudzego kodu rozwiązującego całe postawione zadanie).  
Można korzystać z rozwiązań opisanych w książkach i artykułach, wówczas trzeba podać źródło. 

<li>
Proszę nie traktować mnie jako swojego korektora.
Za przysłanie niedziałających programów, niekompletnych sprawozdań i z błędami zwracam pracę do poprawy i obniżam ocenę. 
Programy można testować i zgłaszać dowolną liczbę razy na zajęciach bez wpływu na ocenę.
</ol>
<br>
<hr>
<a name="sprawo"></a>
<b>Format sprawozdania</b><br>
<p>
Sprawozdanie powinno zawierać:
<ol>
<li>Metadane nt. autorów i projektu: 
imiona, nazwiska, nry indeksów, email do kontaktu,
datę oddania sprawozdania (najlepiej wpisać w momencie wręczenia mi), 
nazwę zadania i nazwę rozwiązania (np. Kolorowanie, algorytm zachłanny).
<li>Opis metody rozwiązania problemu. Trzeba opisać ideę/zasadę na
której opiera się algorytm. Można tu włączyć <u><i>istotne</i></u>
wyjątki z kodu.
<li>Badania efektywnościowe, tzn. wyniki testów czasu działania metody i jakości uzyskanych rozwiązań w zależności od trudności problemu.
Przykładowe instancje testowe zostaną wskazane przy każdym temacie. 
Przeprowadzenie obszerniejszych testów będzie zaletą pracy.
<li>Wnioski. Ciekawe spostrzeżenia nt. działania algorytmu(-ów),
trudności instancji itp. Np. można porównać swoje dwie/trzy metody na
wykresie jakość/czas i stwierdzić, która dominuje nad którą, a które
metody są niezdominowane.
<li>
Załącznik w postaci kodu programu proszę przysłać pocztą 
(może być spakowany jakimś typownym programem, np. w formacie zip, tgz).
Program będzie testowany pod kątem poprawności generowanych rozwiązań.
<li>
W emailu i/lub sprawozdaniu proszę napisać jak skompilować Państwa program i jak go uruchomić.
</ol>
Proszę o dostarczenie sprawozdania w formie <u><b>papierowej</u></b> (z wyjątkiem kodu programu).<br>



<hr>
<a name="tema"></a>
<b>Lista tematów do wyboru</b><br>

<ul type=A>

<li>Szeregowanie parallel tasks (zadań równoległych) wg danych z 
<a href="http://www.cs.huji.ac.il/labs/parallel/workload/">
<b>parallel workload archives</b></a>.
Znaleźć najkrótsze uszeregowanie dla zadanego zestawu zadań. 
Program ma wczytywać dane w tekstowym formacie 
<a href="http://www.cs.huji.ac.il/labs/parallel/workload/swf.html">SWF</a>.
Uwzględnić:
p_j (czas trwania zadania),
r_j (moment gotowości/przybycia), 
size_j (liczbę żądanych/przydzielonych procesorów).
Określają to kolumny 1, 2, 4, 5 w formacie SWF.
Zadania są niepodzielne.<br>
<u>Dodatkowe założenia i zastrzeżenia:</u>
<ol>
<li>Wyniki wyprowadzić w postaci listy linii opisujących uszeregowanie każdego z zadań w formacie:<br>
nr_zadania momentstartu momentzakończenia numeryprzydzielonychprocesorów \n<br>
separatorem w linii mają być spacje. 
Proszę nie umieszczać żadnych innych wyrazów w linii opisującej pojedyncze zadanie.
<li>Proszę zauważyć, że<br>
- w niektórych plikach np. DAS2-fs0-2003-1.swf.gz niektóre zadania mają niekompletne dane,<br>
- w pliku NASA-iPSC-1993-2.1-cln.swf.gz są zadania o zerowym czasie trwania.<br>
Takie zadania trzeba zignorować (przeskoczyć). 
Nie można jednak zmieniać identyfikatorów zadań w wynikowym pliku.
Inaczej, nie można ich przenumerowywać, aby były po kolei w pliku
wynikowym.
Jeszcze innymi słowy, identyfikatory zignorowanych zadań z pliku wejściowego nie pojawią się w pliku wyjściowym.<br> 
<li>Przyjąć, że zawsze MaxNodes=MaxProcs oraz zawsze MaxJobs=MaxRecords.<br>
<li>Umożliwić konstrukcję uszeregowania tylko dla podzbioru N pierwszych zadań
z pliku SWF, gdzie N może być zadane w czasie uruchomienia programu.<br>
<li>Kolejność zadań w wejściowym pliku SWF nie musi być zgodna z r_j.<br>
<li>Proszę zdecydować, czy przydziały procesorów są przyległe
(contiguous), czy nieprzyległe (noncontiguous).
W przydziale przyległym należy zadaniu przydzielić size_j kolejnych
numerów procesorów, np. dla sizej_j=5: 3,4,5,6,7.
W przydziale nieprzyległym procesory mogą mieć numery, które nie są
kolejne np. 2,3,7,19,43.
Szeregowanie z nieprzyległymi przydziałami procesorów wydaje się prostsze.
Można więc ograniczyć się do niego.
Jeżeli jednak ktoś zdecyduje inaczej, to proszę to wyraźnie zaznaczyć w
sprawozdaniu.<br>
<li>W pliku SWF pominąć zadania, dla których nie wszystkie parametery są znane.<br>
</ol>
Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu): 
<a href="test1.txt">test1</a>,
<a href="test2.txt">test2</a>,
<a href="test3.txt">test3</a>.<br>
<u>Instancje do testów efektywnościowych:</u>
LANL-CM5-1994-3.1-cln.swf.gz,
SDSC-SP2-1998-3.1-cln.swf.gz,
DAS2-fs0-2003-1.swf.gz.
Dla każdego pliku należy rozwiązać pierwsze 1, 2, 5, 10, 20, 50, 100, 200
.... zadań.
Limit zadań, które należy osiągnąć powinien wynikać z limitu czasu.
Patrz <a href="#info">uwagi o implementacji</a>.
<br>
<a href="chk_pata.zip">Sprawdzarka</a> windows konsola
różne 
<a href="DLL-rozne.zip">biblioteki dll</a> do niej. 
<br>
<br>

<li>Job-shop.  
Na czym polega problem szeregowania w job-shopie zostało naszkicowane na foliach
101, 102 <a href="http://www.cs.put.poznan.pl/mdrozdowski/dyd/420/szere.html">wykładu</a>,
który kiedyś prowadziłem.
Należy znaleźć dopuszczalne uszeregowanie o minimalnej długości. <br>
Przykładowe instancje testowe są na str. 
<a href="http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt">
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt
</a><br>
oraz (w innym formacie) na str. (instancje Taillarda): 
<a href="http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html">
http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html
</a>.
Opis formatu danych znajduje się w samych plikach.<br>
<u>Dodatkowe założenia i zastrzeżenia:</u>
<ol>
<li>Rozwiązanie podać w postaci: 
długość uszeregowania \n<br> 
momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania1 \n<br> 
momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania2 \n<br> 
momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania3 \n ...<br>
momenty_rozpoczęcia_wykonywania_kolejnych_operacji_ostatniego_zadania \n<br>
gdzie "\n" oznacza znak nowej linii. 
Innymi słowy, liczba o współrzędnych wiersz "i", kolumna "j" 
oznacza moment rozpoczęcia wykonywania operacji "j" zadania "i".<br>
<li>
programy powinny czytać oba typy instancji (mogą zostać przygotowane 2 wersje programu),<br>
<li>
programy muszą umieć rozwiązać instancje tylko dla pewnej zadanej liczby pierwszych zadań, aby można było sporządzić zależność czasu wykonania od liczby zadań,<br>
<li>
zakładamy, że dopuszczalny jest czas wykonania 0  (to oznacza że operację o czasie trwania 0 można przeskoczyć nie przydzielając jej do niczego) oraz powrót zadania na odwiedzoną wcześniej maszynę.<br>
</ol>
Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu, w formacie J.E.Beasleya (orlib)): 
<a href="fs1">fs1</a>,
<a href="fs2">fs2</a>,
<a href="fs3">fs3</a>.
Pocięte pliki z instancjami orlib i Taillarda do testów <a href="js1.ZIP">js1.ZIP</a>.<br>

<u>Instancje do testów efektywnościowych.</u>
W sprawozdaniu muszą się znaleźć pomiary czasu i jakości dla instancji: ta20 do ta25 
oraz czasu dla zwiększającej się od 1 do 20 liczby zadań dla instancji ta25.
Większa liczba testów będzie działać na korzyść przy ocenie pracy.
<br>
<a href="chk_jsorl.exe">Sprawdzarka</a> dla instancji orlib (beasley), Windows konsola.
Różne 
<a href="DLL-rozne.zip">biblioteki dll</a> do niej. 
<br>
<br>



<li>Capacitated Vehicle Routing Problem (CVRP, problem marszrutyzacji z ograniczeniami pojemności).
Na czym polega CVRP można przeczytać na stronach:<br>
<a href="http://neo.lcc.uma.es/radi-aeb/WebVRP/">http://neo.lcc.uma.es/radi-aeb/WebVRP/</a> (przyjmujemy ten opis za wzorcowy),
<a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>,
<a href="http://en.wikipedia.org/wiki/Vehicle_routing_problem">http://en.wikipedia.org/wiki/Vehicle_routing_problem</a>.<br>
<u>Dodatkowe założenia i zastrzeżenia:</u>
<ol>
<li>Brak ograniczeń na długość pojedynczej trasy (route).
<li>Czas załadunku u klienta jest równy 0.
<li>Między wierzchołkami ciężarówki poruszają się po liniach prostych ("lotem ptaka").
<li>Dane wejściowe będą w pliku w formacie:<br>
liczbawierzchołków pojemnośćciężarówki\n<br>
x0 y0\n<br>
x1 y1 d1\n<br>
x2 y2 d2\n<br>
....<br>
xn yn dn<br>
gdzie "\n" oznacza znak nowej linii, 
x0 y0 - współrzędne kartezjańskie magazynu,
xi yi - współrzędne klienta (wierzchołka) "i",
di - zapotrzebowanie klienta "i".
Typy liczb: zapotrzebowania i pojemności - int, współrzędne -
zmiennoprzecinkowe.
Przykładowe instancje w powyższym formacie <a href""></a>.
<li>Rozwiązanie podać w pliku w postaci:<br> 
liczbatras całkowitadługośćwszystkichtras\n <br>
nr_1._wierzchołka_w_1.trasie nr_2._wierzchołka_w_1.trasie ...\n,<br>
...
nr_1._wierzchołka_w_ostatnietrasie nr_2._wierzchołka_w_ostatniejtrasie ...\n<br>
gdzie "\n" oznacza znak nowej linii, separatorem między numerami powinna być spacja lub inna "whitespace".<br>
<li>w rozwiązaniach wierzchołki numerujemy od 1 tak jak w plikach danych (a nie od 0 jak w niektórych plikach z wynikami w ww. repozytoriach sieciowych),
<li>długość trasy należy podać z co najmniej 5 miejscami po przecinku,
<li>plik musi być prawidłowo zamknięty,
<li>nie można przyjmować ograniczenia na rozmiar problemu mniejszego niż w przykładowych instancjach,
</ol>
Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu): 
<a href="cvrp1.vrp">cvrp1.vrp</a>,
<a href="cvrp2.vrp">cvrp2.vrp</a>,
<a href="cvrp3.vrp">cvrp3.vrp</a>.<br>


<u>Instancje do testów efektywnościowych.</u>
Przykładowe instancje do testów w powyższym formacie <a href="cvrp-inst.zip">cvrp-inst.zip</a>.
W sprawozdaniu muszą się znaleźć pomiary czasu i jakości dla instancji: 
F-n135-k7.vrp dla narastającej liczbie wierzchołków od 1 do 134 (licząc od 0).
Większa liczba testów będzie działać na korzyść przy ocenie pracy.<br>
<a href="chkcvrp.exe">Sprawdzarka</a> Windows konsola.
Różne <a href="DLL-rozne.zip">biblioteki dll</a> do niej. 
</ul>

<hr>
<a name="info"></a>
<b>Uwagi nt. implementacji</b><br>
<p>
<ol>
<li>Jak określić kiedy metaheurystyka ma się zatrzymać? Są dwa
wyjścia.<br>
a) Jeżeli algorytm jest zdefiniowany tak, że znamy optymalną
wartość funkcji celu, to algorytm może zatrzymać się po jej
osiągnięciu.<br>
b) Jeżeli optimum nie jest znane, to trzeba zatrzymać się po pewnym
czasie. Ze względów praktycznych algorytmy zachłanne nie powinny działać
dłużej niż kilka sekund, a algorytmy takie jak BB, GA, Tabu nie powinny
działać dłużej niż kilka (góra kilkanaście) minut, aby możliwa była
weryfikacja ich działania na zajęciach. Trzeba tak dobrać liczbę 
iteracji, aby ten czas nie był przekraczany. 
Przyjmijmy, że limit czasu dla testów do sprawozdania to 10 minut.
Do weryfikacji poprawności rozwiązania na zajęciach przyjmijmy limit 5
minut.
<br>
<li>Strojenie (tuning) metaheurystyk.<br>
Jeżeli ktoś z Państwa implementuje jakąś metaheurystykę, to proszę zwróćić uwagę,
że metaheurystyki zwykle mają szereg "magicznych" parametrów sterujących ich działaniem. 
Na przykład: 
tabu search - długość listy tabu, rozmiar przeszukiwanego sąsidztwa,
genetic search - rozmiar populacji, prawdopodobieństwo mutacji,
simulated annealing - sposób zmieniania temperatury,
wszystkie takie algorytmy - warunek stopu (np. liczba iteracji, czas działania
do zatrzymania).
Te wszystkie parametry <u>trzeba sensownie dobrać</u>. 
Zwykle wymaga to testowania i eksperymentalnego dobierania. 
Wyniki takich testów trzeba opisać i objaśnić w sprawozdaniu.
Zwykle wiązanie <i>ad hoc</i> tych "magicznych" liczb ze strukturą instancji nie
jest dobrym pomysłem.
Brak strojenia oznacza, że metaheurystka nie została prawidłowo użyta.
</ol>

<hr>
<b>Uwagi organizacyjne</b><br>
<p>
<ol>
<li>
Znalazłeś/Znalazłaś błąd? Informuj! 
<li>
Za znalezienie błędu (wykazanie błędnego działania) sprawdzarki +1 stopień do oceny końcowej.
IInformacja o błędzie musi zawierać przykładowe pliki wejściowe z objaśnieniem
co działa niepoprawnie.
<li>
Za znalezienie błędów w danych +0.1 do oceny końcowej.
<li>
Zajęcia w dniach 11 i 14 października 2011 zostają odwołane.
Osoby z 11  proszę o przyjście na zajęcia 18 października,
a osoby z 14 na 21 października.
</ol>

<p>
<HR>
<P ALIGN="right">
<i>MD.</i>Ostatnia zmiana :<SCRIPT LANGUAGE="JavaScript">
<!--
        document.write(document.lastModified);
// -->
</SCRIPT>
</P>

</body>
</HTML>
